package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-01-29 23:15
 */
public class Q516 {
    public int longestPalindromeSubseq(String ss) {
        if (ss == null || ss.length() == 0) {
            return 0;
        }

        char[] s = ss.toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];

        //init
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = 2;
            } else {
                dp[i][i + 1] = 1;
            }
        }

        //注意这里的遍历方式
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                if (s[i] == s[j]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
                }
            }
        }

        return dp[0][n - 1];
    }


    char[] s;
    int n;
    int[][] dp;

    public int longestPalindromeSubseq2(String ss) {
        if (ss == null || ss.length() == 0) {
            return 0;
        }

        s = ss.toCharArray();
        n = s.length;
        dp = new int[n][n];

        //init
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = -1; //没计算初始化为-1
            }
        }


        Compute(0, n - 1);
        return dp[0][n - 1];
    }

    private void Compute(int i, int j) {
        //记忆化搜索
        if (dp[i][j] != -1) {
            return;
        }

        if(i == j) {
            dp[i][j] = 1;
            return;
        }

        if(i + 1 == j){
            dp[i][j] = s[i] == s[j] ? 2 : 1;
            return;
        }

        //回溯
        Compute(i + 1, j);
        Compute(i, j - 1);
        Compute(i + 1, j - 1);

        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
        if(s[i] == s[j]){
            dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
        }
    }
}
